排列

Time Limit: 10 Sec Memory Limit: 128 MB

Description

给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。

例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。

Input

输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。

Output

每个数据仅一行，表示能被d整除的排列的个数。

Sample Input

7
　　000 1
　　001 1
　　1234567890 1
　　123434 2
　　1234 7
　　12345 17
　　12345678 29

Sample Output

1
　　3
　　3628800
　　90
　　3
　　6
　　1398

HINT

s的长度不超过10, 1<=d<=1000, 1<=T<=15

Solution

我们运用状压DP，令 f[j][opt] 表示当前余数为 j，状态为opt的方案。

状态记录的是：各个数字被用了几次。

那么我们就可以状压了。先DFS出每个状态，记sum[k]表示后缀积，那么显然 从 opt 转移到 第k个数字多用一次的状态 就是 opt + sum[k + 1]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;  
typedef long long s64;

const int ONE = 20005;

int T, n, m;
int num;
int vis[ONE], Num[20], sum[20];
int f[1005][20005];
int Sta[ONE][10];
char ch[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 ) 
        if(c=='-')Q=-1; 
    res=c-48;     
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;    
    return res*Q;
}

void Dfs(int T)
{
    if(T > 10)
    {
        num++;
        for(int i = 0; i <= 9; i++)
            Sta[num][i] = vis[i];
        return;
    }

    for(int i = 0; i <= Num[T]; i++)
        vis[T] = i, Dfs(T + 1);
}

void Deal()
{
    memset(f, 0, sizeof(f));
    memset(Num, 0, sizeof(Num));
    memset(sum, 0, sizeof(sum));
    num = 0;
    scanf("%s", ch + 1);    m = get();
    n = strlen(ch + 1);

    for(int i = 1; i <= n; i++) Num[ch[i] - '0']++;
    sum[10] = 1; for(int i = 9; i >= 0; i--) sum[i] = sum[i + 1] * (Num[i] + 1);

    Dfs(0);

    f[0][1] = 1;
    for(int opt = 1; opt <= num; opt++)
        for(int j = 0; j < m; j++)
            if(f[j][opt])
                for(int k = 0; k <= 9; k++)
                {
                    if(Sta[opt][k] >= Num[k]) continue; 
                    int to = opt + sum[k + 1];
                    f[(j * 10 + k) % m][to] += f[j][opt];
                }

    printf("%d\n", f[0][num]);
}

int main()
{
    T = get();
    while(T--)
        Deal();
}